In the Service Oriented Architecture （SOA）， an improved Krill Herd algorithm PRKH with adaptive crossover and random perturbation operator was proposed to solve the problem of easily falling into local optimum and high time cost in the process of service composition optimization. Firstly， a service composition optimization model was established based on Quality of Service （QoS）， and the QoS calculation formulas and normalization methods under different structures were given. Then， based on the Krill Herd （KH） algorithm， the adaptive crossover probability and the random disturbance based on the actual offset were added to achieve a good balance between the global search ability and the local search ability of krill herd. Finally， through simulation， the proposed algorithm was compared with KH algorithm， Particle Swarm Optimization （PSO） algorithm， Artificial Bee Colony （ABC） algorithm and Flower Pollination Algorithm （FPA）. Experimental results show that the PRKH algorithm can find better QoS composite services faster.